public class LongestPalindromeSubseq {
    /*
    题目: 最长回文子序列
    给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

    子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

    https://leetcode.cn/problems/longest-palindromic-subsequence
     */
    // 该问题也可以等价为 : s 和 [反转后的] s 的最长公共子序列
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // [i, j] 中最长回文子序列的长度
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i ++)   dp[i][i] = 1;

        int maxLength = 1;
        for (int i = n; i >= 1; i --) {
            for (int j = i + 1; j <= n; j ++) {
                if (s.charAt(i - 1) == s.charAt(j - 1)) {
                    if (i + 1 == j) dp[i][j] = 2;
                    else            dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {  // 如果不相等
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // 舍弃其中一个某字符 的 最大值
                }
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }

        return maxLength;
    }
    
    /*
    题目: 让字符串成为回文串的最少操作次数
    给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

    请你返回让 s 成为回文串的 最少操作次数 。

    https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
     */

    public int minInsertions(String s) {
        // 核心思路: 寻找最长回文子序列
        // 再将剩下的 [零散的] 继续构成回文串
        int n = s.length();

        // 表示 [i, j] 中最长回文子序列的长度
        int maxLength = 1;
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i ++)   dp[i][i] = 1;

        for (int i = n; i >= 1; i --) {
            for (int j = i + 1; j <= n; j ++) {
                if (s.charAt(i - 1) == s.charAt(j - 1)) {
                    if (i + 1 == j) { // 只有 两个元素 构成的回文串
                        dp[i][j] = 2;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }

        return n - maxLength;
    }
}
